/*
 * @Author: szx
 * @Date: 2021-11-06 13:44:52
 * @LastEditTime: 2021-11-06 13:57:37
 * @Description:
 * @FilePath: \leetcode\100-199\198\198.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
// class Solution {
//    public:
//     int rob(vector<int>& nums) {
//         int n = nums.size();
//         vector<int> dp(n + 1, 0);
//         dp[1] = nums[0];
//         for (int i = 2; i <= n; i++) {
//             dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
//         }
//         return max(dp[n], dp[n - 1]);
//     }
// };

class Solution {
   public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int q = 0, p = 0, r = nums[0];

        for (int i = 2; i <= n; i++) {
            q = p;
            p = r;
            r = max(p, q + nums[i-1]);
        }
        return max(r, p);
    }
};